//单词搜索
class Solution {
    public:
        string replaceWords(vector<string>& dictionary, string sentence) {
            int n = sentence.size();
            unordered_set<string> hash;
            for(auto& e : dictionary)
            {
                hash.insert(e);
            }
            // for(auto& e : hash)
            // {
            //     cout << e << " ";
            // }
            //ret返回结果
            string ret = "";
            //word寻找的词根
            string word = "";
            for(int i = 0; i < n; i++)
            {
                word += sentence[i];
                if(hash.find(word) != hash.end())
                {
                    ret = ret + word;
                    while(i < n && sentence[i] != ' ')
                        i++;
                    if(i < n)
                        ret += " ";
                    word = "";
                }
                //如果没找到就加入
                if(sentence[i] == ' ' || i == n - 1)
                {
                    ret = ret + word;
                    word = "";
                }
            }
            return ret;
        }
    };